package sword2offer;

/**
 * <p>
 * 整数除法
 * </p>
 *给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 *
 * 解法： 不能用循环a-b
 * 初始化返回值ret = 0
 * 如果换成如果被除数大于除数，则除数扩大一倍
 * 若被除数仍大于除数，这除数再次扩大一倍
 * 直到除数下一次翻倍比被除数大时，将被除数减去除数，并将ret+=除数扩大的倍数，结束这一轮循环
 * 重复2、3、4，直到被除数小于除数，终止循环并返回ret即可。
 *
 * 作者：qingfengpython
 * 链接：https://leetcode-cn.com/problems/xoh6Oh/solution/shua-chuan-jian-zhi-offer-day01-zheng-sh-8u0s/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author LovelyBigDuck
 * @date 2022/3/13 20:28
 */
public class S_001 {
    class Solution {
        public int divide(int a, int b) {
            int flag = 0;
            if (a > 0) {
                a = -a;
                flag += 1;
            }

            if (b > 0) {
                b = -b;
                flag += 1;
            }
            int ret = calc(a, b);
            if (flag != 1 && ret == Integer.MIN_VALUE) {
                ret++;
            }
            return flag == 1 ? ret : -ret;
        }

        private int calc(int a, int b) {
            int ret = 0;
            while (a <= b) {
                int cnt = 1;
                int val = b;
                while (val >= Integer.MIN_VALUE >> 1  && a <= val << 1) {
                    cnt += cnt;
                    val += val;
                }
                ret -= cnt;
                a -= val;
            }
            return ret;
        }
    }

    public int divide1(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1)
            return Integer.MAX_VALUE;
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            // 首先，右移的话，再怎么着也不会越界
            // 其次，无符号右移的目的是：将 -2147483648 看成 2147483648

            // 注意，这里不能是 (a >>> i) >= b 而应该是 (a >>> i) - b >= 0
            // 这个也是为了避免 b = -2147483648，如果 b = -2147483648
            // 那么 (a >>> i) >= b 永远为 true，但是 (a >>> i) - b >= 0 为 false
            if ((a >>> i) - b >= 0) { // a >= (b << i)
                a -= (b << i);
                // 代码优化：这里控制 res 大于等于 INT_MAX
                if (res > Integer.MAX_VALUE - (1 << i)) {
                    return Integer.MIN_VALUE;
                }
                res += (1 << i);
            }
        }
        // bug 修复：因为不能使用乘号，所以将乘号换成三目运算符
        return sign == 1 ? res : -res;
    }
}
